package com.zlk.algorithm.algorithm.sort.merge;

/**
 * @program: algorithm
 * @ClassName CountOfRangeSum
 * https://leetcode.cn/problems/count-of-range-sum/description/
 * 前准和数组要用long  int数组会报错 todo
 * @author: slfang
 * @create: 2024-01-17 15:09
 * @Version 1.0
 **/
public class CountOfRangeSum {

    int countRangeSum(int[] nums,int lower,int upper){
        if(nums.length<1||nums==null){
            return 0;
        }
//        数组值 : 3   2  -1  4   5
//        前缀和 : 3   5   4  8  13
//        下标值 : 0   1   2  3   4
//        假设，我们想知道，累加和落在[4 ~ 5]范围上的子数组有多少个？
        //arr[0…3]的整体累加和 == 8，然后注意看：
        //
        //找：子数组必须以3位置(数字4)结尾的情况下，累加和落在[4 ~ 5]范围上的子数组。
        //
        //就是找：4之前所有的前缀和里，有哪些前缀和在[3, 4]范围上。3 = 8 - 5，4 = 8 - 4。也就是你截图里截的意思。
        //
        //转化了！为什么？因为等效的！怎么等效？
        //
        //比如，arr[0…2]这个前缀和等于4，在[3, 4]范围上。
        //
        //因为arr[0…3]的累加和 == 8，arr[0…2]的累加和 == 4，所以arr[3…3] = 8 - 4 = 4，arr[3…3]这个子数组落在了[4 ~ 5]范围上！
        //
        //再比如，arr[0…1]这个前缀和等于5，不在[3, 4]范围上。
        //
        //因为arr[0…3]的累加和 == 8，arr[0…1]的累加和 == 5，所以arr[2…3] = 8 - 5 = 3，arr[2…3]这个子数组没有落在[4 ~ 5]范围上！
        //
        //再比如，arr[0…0]这个前缀和等于3，在[3, 4]范围上。
        //
        //因为arr[0…3]的累加和 == 8，arr[0…0]的累加和 == 3，所以arr[1…3] = 8 - 3 = 5，arr[1…3]这个子数组落在了[4 ~ 5]范围上！
        //你求必须以i位置结尾的时候，有多少个子数组累加和在[ a, b ] 范围，
        //
        //就是求：
        //
        //假设 0…i 整体的累加和是sum，就是求i之前有多少前缀和，落在[sum - b, sum - a]范围上。
        //可能符合要求的子数组有、arr[1,3]、arr[2,3]、arr[3,3]. 如果要使这些子数组能够落在[4~5]上，
        // 就必须使前面的前缀和数组能够落在[3,4]上，否则3位置(数字4)的前缀和是不可能得到8的。
        //int[] preSumArr = buildPreSumArr(nums);
        //将原目标转换成 求存在多少个以 i为底结束 前缀和在范围中 ,累加就等于的所求的。

        /**
         * 构建前缀和数组
         */
        long[] sum = new long[nums.length];
        sum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        return sortMerage(sum,0,sum.length-1,lower,upper);
    }


    private int sortMerage(long[] preSumArr, int l, int r, int lower, int upper) {
        //        数组值 : 3   2  -1  4   5
        //        前缀和 : 3   5   4  8  13
        //        下标值 : 0   1   2  3   4
        if(l==r){//表示0 到 r 的原数组累加和 也就是前缀树数组的当前值
            //判断在不在范围内
//            if(preSumArr[l]>=lower&&preSumArr[l]<=upper){
//                return 1;
//            }else{
//                return 0;
//            }  优化
            return preSumArr[l]>=lower&&preSumArr[l]<=upper?1:0;
        }
        int mid = l+((r-l)>>1);
        return sortMerage(preSumArr,l,mid,lower,upper)+sortMerage(preSumArr,mid+1,r,lower,upper)
                +merage(preSumArr,l,mid,r,lower,upper);
    }

    private int merage(long[] preSumArr, int l, int mid, int r, int lower, int upper) {
        //        前缀和 : 3   4   5      8  13           lower 4   upper 5
        //                                              3,4     8,9
        //
        //左侧存在两个不回退的范围指针  右侧一个不回退单指针
        int lLowerIndex = l;
        int rUpperIndex = l;
        int rIndex = mid+1;
        int count = 0;

        while (rIndex<=r){
            long rVal = preSumArr[rIndex++];
            long newLower = rVal-upper;
            long newUpper = rVal-lower;
            while (rUpperIndex<=mid&&preSumArr[rUpperIndex]<=newUpper){
                rUpperIndex++;
            }
            while (lLowerIndex<=mid&&preSumArr[lLowerIndex]<newLower){
                lLowerIndex++;
            }
            count+=rUpperIndex-lLowerIndex;

        }

        rIndex= mid+1;
        int lIndex = l;
        long[] temp = new long[r-l+1];
        int index =0;
        while (lIndex<=mid&&rIndex<=r){ //10, 2, 4, 5, 4, 6
            temp[index++]=preSumArr[lIndex]<=preSumArr[rIndex]?preSumArr[lIndex++]:preSumArr[rIndex++];
        }
        while (lIndex<=mid){
            temp[index++] = preSumArr[lIndex++];
        }
        while (rIndex<=r){
            temp[index++] = preSumArr[rIndex++];
        }
        for (int i = 0; i < temp.length; i++) {
            preSumArr[l+i] = temp[i];
        }
        return count;
    }


}
